Hierarchical data structures are a widely used data abstraction for the organization and classification of information. Hierarchies have been utilized in a vast array of applications, including corporate organizational charts, computer file systems and the stock market. Given the ubiquitous nature of these data structures, hierarchical visualization techniques have received attention within the Information Visualization community.
One method for visualizing hierarchical data is the Treemap. See, for example, B. Johnson and B. Shneiderman, “Tree-Maps: A Space-Filling Approach to the Visualization of Hierarchical Information Structures,” Proc of IEEE Visualization (1991). Generally, the Treemap is a space-tilling visualization technique. A recursive spatial sub-division algorithm is used to create an arrangement of nested rectangles. The size of each rectangle encodes the value of an attribute of the data set (e.g., the size of a file or directory when visualizing a file system) while the nested rectangles represent children (e.g., files and sub-directories contained within a directory).
A number of techniques have been proposed or suggested to make Treemaps a more effective visualization technique. For example, a number of proposed techniques have attempted to reduce the often high aspect ratios of rectangular regions produced by the original algorithm. However, these improvements to aspect ratio typically come at the cost of increased instability. None of these algorithms offer both full stability and ideal aspect ratios. As a result, Treemap applications have largely been applied to relatively static data sets where the sizes of cells do not change significantly over time.
The resulting instability that afflicts most Treemap layout algorithms manifests itself during animation as potentially large discontinuous jumps in the position and dimensions of individual cells. These jumps, most problematic for algorithms that produce the best aspect ratios, are highly disruptive to users. As a result, several techniques have been developed to allow improved temporal animations of Treemap visualizations.
Voronoi Treemaps have been proposed for visualizing software structures. See., e.g., M. Balzer and O. Deussen, “Voronoi Treemaps,” IEEE InfoVis, 7 (Washington, D.C., 2005); or M. Balzer et al., “Voronoi Treemaps for the Visualization of Software Structures,” Proc. of ACM Symposium on Software Visualization (2005), each incorporated by reference herein. Generally, Voronoi Treemaps use an optimization-based layout algorithm to create Treemaps composed of nested convex polygonal shapes. The resulting regions typically have excellent aspect ratios. However, existing Voronoi Treemap algorithms do not produce layouts suitable for animation.
The inventor has recognized that a need still exists for a Treemap layout having both stability during animation and desirable aspect ratios. A further need exists for a Treemap layout that enables smooth continuous animation between states when presented with dynamic data.